package leetcode_700;

import java.util.LinkedList;
import java.util.Queue;

import helpclass.TreeNode;

/**
 *@author 周杨
 *AddOneRowToTree_623 给二叉树某高度增加一行元素
 *describe:用深搜 AC 30%
 *2018年9月20日 上午9:57:57
 */
public class AddOneRowToTree_623 {
	 public TreeNode addOneRow(TreeNode root, int v, int d) {
		 if (d == 1) {
	            TreeNode newNode = new TreeNode(v);
	            newNode.left = root;
	            return newNode;
	        }
	        Queue<TreeNode> queue = new LinkedList<>();
	        queue.offer(root);
	        while (d-- >= 1) {
	            int size = queue.size();
	            for (int i = 0; i < size; i++) {
	                TreeNode cur = queue.poll();
	                if (d == 1) {
	                    TreeNode newleft = new TreeNode(v);
	                    TreeNode newright = new TreeNode(v);
	                    newleft.left = cur.left;
	                    newright.right = cur.right;
	                    cur.left = newleft;
	                    cur.right = newright;
	                } else {
	                    if (cur.left != null) queue.offer(cur.left);
	                    if (cur.right != null) queue.offer(cur.right);
	                }
	            }
	        }
	        return root;  
	 }
}
